		TITLE	QUICK_RELOCS - Copyright (c) SLR Systems 1994

		INCLUDE	MACROS
		INCLUDE	RELOCSS
		INCLUDE	SEGMSYMS

		PUBLIC	QUICK_RELOCS


		.DATA

		EXTERNDEF	FIRST_RELOC_GINDEX:DWORD

		EXTERNDEF	RELOC_GARRAY:STD_PTR_S


		.CODE	PASS2_TEXT

		EXTERNDEF	GET_NEW_LOG_BLK:PROC


QUICK_VARS	STRUC

QDELTA_BP		DD	?
QLEFT_NUMBER_BP		DD	?
QRIGHT_NUMBER_BP	DD	?
QLEFT_PTR_BP		DD	?
QRIGHT_PTR_BP		DD	?
QMIDDLE_PTR_BP		DD	?
QN_BUFFER_PTR_BP	DD	?
QN_PTR_BP		DD	?

QUICK_VARS	ENDS


FIX	MACRO	X

X	EQU	([EBP-SIZE QUICK_VARS].(X&_BP))

	ENDM


FIX	QDELTA
FIX	QLEFT_NUMBER
FIX	QRIGHT_NUMBER
FIX	QLEFT_PTR
FIX	QRIGHT_PTR
FIX	QMIDDLE_PTR
FIX	QN_BUFFER_PTR
FIX	QN_PTR

QEXCHANGE2	MACRO

		MOV	EAX,[ESI]
		MOV	EBX,[EDI]

		MOV	[EDI],EAX
		MOV	[ESI],EBX

		ENDM


QUICK_RELOCS	PROC
		;
		;USE QUICKSORT ALGORITHM TO SORT RELOCATIONS TABLE IN NUMERIC
		;ORDER
		;
		;
		;FIRST COPY INDEXES TO ANOTHER AREA FOR EASY SORTING
		;
		PUSHM	EBP,EDI,ESI,EBX		;SAVE THAT STACK FRAME

		MOV	EBP,ESP
		ASSUME	EBP:PTR QUICK_VARS
		SUB	ESP,SIZE QUICK_VARS

		MOV	QN_BUFFER_PTR,EAX
		CALL	QUICK_INIT

		CALL	QUICK_REL

		MOV	ESP,EBP

		POPM	EBX,ESI,EDI,EBP

		RET

QUICK_RELOCS	ENDP


QUICK_NUMERIC_1	PROC	NEAR	PRIVATE

QUICK_2:
		;
		;JUST SORT THE TWO AND RETURN...
		;
		CALL	Q_SET_LEFT_BLOCK	;DS:SI

		CALL	Q_SET_RIGHT_BLOCK	;ES:DI

		JMP	QR_SORT2


QUICK3:
		POP	EAX
QUICK2_FINISH:
QUICK_DONE:

		RET

QUICK_REL::
		;
		;OK BOYS, HERE GOES A QUICK-SORT IMPLEMENTATION...
		;
		;ESI IS LEFT SYMBOL #, EDI IS RIGHT SYMBOL #
		;
		MOV	ECX,EDI
QUICK_REL_1:
		SUB	ECX,ESI
		JNA	QUICK_DONE	;RIGHT <= LEFT, QUIT
		;
		;WHAT ABOUT REAL SMALL CX ?
		;
		INC	ECX
		JZ	QUICK_DONE	;NO SYMBOLS AT ALL...

		CMP	ECX,2
		JZ	QUICK_2

		MOV	QDELTA,ECX

		SHR	ECX,1
		PUSH	ESI

		ADD	ECX,ESI		;HALF WAY IN BETWEEN...
		MOV	QRIGHT_NUMBER,EDI

		MOV	QLEFT_NUMBER,ESI
		CALL	Q_SET_LEFT_BLOCK	;DS:SI

		MOV	QLEFT_PTR,ESI
		CALL	Q_SET_RIGHT_BLOCK	;ES:DI

		MOV	QRIGHT_PTR,EDI
		CALL	Q_SET_MIDDLE_BLOCK	;ES:DI

		MOV	QMIDDLE_PTR,EDI
		;
		;DO THREE-SOME SORT
		;
		;IF LEFT>MIDDLE, XCHG LEFT&MIDDLE
		;
		CALL	QR_SORT2
		;
		;IF LEFT > RIGHT, XCHG LEFT&RIGHT
		;
		MOV	EDI,QRIGHT_PTR
		CALL	QR_SORT2
		;
		;LASTLY, IF MIDDLE > RIGHT, XCHG MIDDLE&RIGHT
		;
		MOV	ESI,QMIDDLE_PTR
		CALL	QR_SORT2

		CMP	QDELTA,3
		JZ	QUICK3
		;
		;NOW XCHG MIDDLE WITH RIGHT-1
		;
		CALL	DEC_RIGHT_ESDI

		QEXCHANGE2

		MOV	EAX,QRIGHT_NUMBER	;SAVE RIGHTY
		;
		;DEFINE TEST SYMBOL FROM RIGHT END (ORIGINALLY FROM MIDDLE)
		;
		MOV	ESI,[EDI]		;GET RIGHT SYMBOL VALUE
		CONVERT	ESI,ESI,RELOC_GARRAY
		ASSUME	ESI:PTR RELOC_STRUCT

		PUSH	EAX
		CALL	DEC_RIGHT_ESDI

		MOV	ECX,[ESI]._RL_FLAGS
		MOV	EBX,[ESI]._RL_OS2_NUMBER

		AND	CH,07
		MOV	QRIGHT_PTR,EDI

		CMP	EBX,100H
		JB	NOT_MODULE

		CONVERT	EBX,EBX,IMPMOD_GARRAY
		ASSUME	EBX:PTR IMPMOD_STRUCT

		MOV	EBX,[EBX]._IMPM_NUMBER
		ASSUME	EBX:NOTHING
NOT_MODULE:
		MOV	ESI,QLEFT_PTR
		ASSUME	ESI:NOTHING
		CALL	INC_LEFT_DSSI
		;
		;SCAN FROM LEFT UNTIL SOMETHING FOUND >= CX:BX
		;
		MOV	EDX,QLEFT_NUMBER
QNL_AGAIN:
QNL_LOOP:
		;
		;COMPARE LEFT SYMBOL
		;
		MOV	EDI,[ESI]			;GET NEXT INDEX
		ADD	ESI,4

		CONVERT	EDI,EDI,RELOC_GARRAY
		ASSUME	EDI:PTR RELOC_STRUCT

		MOV	EAX,[EDI]._RL_FLAGS

		AND	AH,7

		CMP	EAX,ECX
		JC	QNL_NEXT

		MOV	EAX,[EDI]._RL_OS2_NUMBER
		JNZ	QNL_TRY_RIGHT

		CMP	EAX,100H
		JB	QNL_N_1

		CONVERT	EAX,EAX,IMPMOD_GARRAY
		ASSUME	EAX:PTR IMPMOD_STRUCT

		MOV	EAX,[EAX]._IMPM_NUMBER
		ASSUME	EAX:NOTHING
QNL_N_1:
		CMP	EAX,EBX
		JNC	QNL_TRY_RIGHT
QNL_NEXT:
		LEA	EAX,[EDX+1]
		INC	EDX

		TEST	EAX,PAGE_SIZE/4 - 1
		JNZ	QNL_LOOP

		MOV	ESI,EDX
		CALL	Q_SET_LEFT_BLOCK

		JMP	QNL_LOOP

QNL_TRY_RIGHT:
		;
		;OOPS, CHANGE AND SCAN FROM OTHER DIRECTION
		;
		SUB	ESI,4
		MOV	EDI,QRIGHT_PTR
		ASSUME	EDI:NOTHING

		MOV	QLEFT_NUMBER,EDX
		MOV	EDX,QRIGHT_NUMBER

		MOV	QLEFT_PTR,ESI
		;
		;SCAN FROM RIGHT UNTIL SOMETHING FOUND <= CX:BX
		;
QNR_LOOP:
		MOV	ESI,[EDI]
		SUB	EDI,4

		CONVERT	ESI,ESI,RELOC_GARRAY
		ASSUME	ESI:PTR RELOC_STRUCT

		MOV	EAX,[ESI]._RL_FLAGS

		AND	AH,7

		CMP	EAX,ECX
		JC	QNR_SWAP

		MOV	EAX,[ESI]._RL_OS2_NUMBER
		JNZ	QNR_NEXT

		CMP	EAX,100H
		JB	QNR_N_1

		CONVERT	EAX,EAX,IMPMOD_GARRAY
		ASSUME	EAX:PTR IMPMOD_STRUCT

		MOV	EAX,[EAX]._IMPM_NUMBER
		ASSUME	EAX:NOTHING
QNR_N_1:
		CMP	EAX,EBX
		JBE	QNR_SWAP
QNR_NEXT:
		MOV	EAX,EDX
		DEC	EDX

		TEST	EAX,PAGE_SIZE/4-1
		JNZ	QNR_LOOP

		MOV	EDI,EDX
		CALL	Q_SET_RIGHT_BLOCK

		JMP	QNR_LOOP

QNR_SWAP:
		;
		;SWAP INDEXES IN TABLE PLEASE
		;
		ADD	EDI,4
		MOV	ESI,QLEFT_PTR
		ASSUME	ESI:NOTHING

		MOV	QRIGHT_PTR,EDI
		MOV	EAX,QLEFT_NUMBER

		MOV	QRIGHT_NUMBER,EDX
		CMP	EAX,EDX

		MOV	EAX,[ESI]
		JNC	QN_DONE1		;SAME, CANNOT SWAP

		MOV	EDX,[EDI]
		MOV	[EDI],EAX

		MOV	[ESI],EDX
		;
		;MOVE BOTH POINTERS
		;
		CALL	DEC_RIGHT_ESDI

		MOV	QRIGHT_PTR,EDI
		CALL	INC_LEFT_DSSI

		MOV	EDX,QLEFT_NUMBER
		MOV	EAX,QRIGHT_NUMBER

		CMP	EAX,EDX
		JAE	QNL_AGAIN		;JUMP IF ANY LEFT
QN_DONE1:
		;
		;SWAP R+1 WITH ORIGINAL PTR...
		;
		POP	EDI		; THIS BECOMES i

		PUSH	EDI
		CALL	Q_SET_RIGHT_BLOCK

		QEXCHANGE2		;SWAP THEM...
		;
		;DETERMINE WHICH HALF WILL BE PROCESSED...(WE WANT TO DO SMALLER HALF)
		;
		POP	ECX		;ORIGINAL RIGHTY - WHERE MIDDLE WAS STORED
		POP	EDX		;ORIGINAL LEFT

		INC	ECX
		MOV	EAX,QRIGHT_NUMBER

		MOV	EBX,ECX
		MOV	EDI,QLEFT_NUMBER

		SUB	EAX,EDX
		SUB	EBX,EDI

		CMP	EAX,EBX
		JC	QN_DONE2
		;
		;LETS SAY DO SECOND HALF FIRST
		;
		MOV	EAX,QRIGHT_NUMBER
		PUSH	EDX		;SAVE ORIGINAL LEFT NUMBER

		PUSH	EAX		;RIGHT TO USE THERE
		LEA	ESI,[EDI+1]

		MOV	EDI,ECX
		CALL	QUICK_REL

		POPM	EDI,ESI

		MOV	ECX,EDI
		JMP	QUICK_REL_1

QN_DONE2:
		;
		;LETS SAY DO FIRST HALF FIRST
		;
		INC	EDI
		MOV	ESI,EDX

		PUSH	EDI
		PUSH	ECX

		MOV	EDI,QRIGHT_NUMBER
		CALL	QUICK_REL

		POPM	EDI,ESI

		MOV	ECX,EDI
		JMP	QUICK_REL_1

QUICK_NUMERIC_1	ENDP


QUICK_INIT	PROC	NEAR	PRIVATE
		;
		;DO SETUP FOR A QUICKSORT
		;
		MOV	ECX,QN_BUFFER_PTR

		MOV	EAX,[ECX]
		ADD	ECX,4

		TEST	EAX,EAX
		JNZ	L51$

		MOV	QN_PTR,ECX		;PLACE FOR BLOCK #'S
		CALL	QUICK_ANOTHER_BLOCK

		MOV	EDX,FIRST_RELOC_GINDEX
		XOR	ECX,ECX

		TEST	EDX,EDX
		JZ	L29$
L2$:
L26$:
		CMP	EDI,PAGE_SIZE
		JZ	L265$
L266$:
		MOV	DPTR [EBX+EDI],EDX
		ADD	EDI,4

		CONVERT	EDX,EDX,RELOC_GARRAY
		ASSUME	EDX:PTR RELOC_STRUCT

		MOV	EDX,[EDX]._RL_NEXT_RELOC_GINDEX

		TEST	EDX,EDX
		JNZ	L2$
L29$:
		JMP	INIT_FINAL

L265$:

		CALL	QUICK_ANOTHER_BLOCK

		JMP	L266$

L405$:
		CALL	QUICK_ANOTHER_BLOCK

		JMP	L406$

INIT_FINAL:
		CMP	EDI,PAGE_SIZE
		JZ	L405$
L406$:
		XOR	EAX,EAX			;MARK END OF INDEXES WITH A ZERO

		MOV	[EBX+EDI],EAX
		ADD	EDI,4
		;
		;NOW WE GET READY TO SORT!
		;
		;HOW MANY SYMBOLS ARE THERE?
		;
		MOV	ECX,QN_BUFFER_PTR
		MOV	EAX,QN_PTR

		SHR	EDI,2
		SUB	EAX,ECX

		SUB	EAX,8

		SHL	EAX,PAGE_BITS-4

		ADD	EAX,EDI

		MOV	[ECX],EAX
L51$:
		MOV	ECX,QN_BUFFER_PTR

		MOV	EDI,[ECX]
		;
		;EDI IS # OF SYMBOLS
		;
		XOR	EAX,EAX
		XOR	ESI,ESI			;SI (LEFT) SYMBOL IS 0

		DEC	EAX
		SUB	EDI,2			;DI (RIGHT) SYMBOL IS LAST_SYMBOL

		RET

QUICK_INIT	ENDP


QUICK_ANOTHER_BLOCK	PROC	NEAR	PRIVATE
		;
		;ES:DI:AX
		;
		MOV	EDI,QN_PTR
		CALL	GET_NEW_LOG_BLK	;CAN STAY IN FASTER MEMORY...

		MOV	[EDI],EAX
		ADD	EDI,4

		MOV	EBX,EAX
		MOV	QN_PTR,EDI

		MOV	DPTR [EDI],0
		XOR	EDI,EDI

		RET

QUICK_ANOTHER_BLOCK	ENDP


Q_SET_LEFT_BLOCK	PROC	NEAR	PRIVATE
		;
		;ESI IS SYMBOL #
		;SET ESI TO BE LEFT POINTER...
		;
		PUSH	ECX
		MOV	EAX,ESI

		SHR	EAX,PAGE_BITS-2
		MOV	ECX,QN_BUFFER_PTR

		AND	ESI,PAGE_SIZE/4-1

		SHL	ESI,2
		MOV	EAX,[ECX+EAX*4+4]

		POP	ECX
		ADD	ESI,EAX

		RET

Q_SET_LEFT_BLOCK	ENDP


Q_SET_RIGHT_BLOCK	PROC	NEAR	PRIVATE
		;
		;SET EDI TO BE RIGHT POINTER...
		;
		PUSH	ECX
		MOV	EAX,EDI

		SHR	EAX,PAGE_BITS-2
		MOV	ECX,QN_BUFFER_PTR

		AND	EDI,PAGE_SIZE/4-1

		SHL	EDI,2
		MOV	EAX,[ECX+EAX*4+4]	;LOGICAL BLOCK ADDRESS

		POP	ECX
		ADD	EDI,EAX

		RET

Q_SET_RIGHT_BLOCK	ENDP


Q_SET_MIDDLE_BLOCK	PROC	NEAR	PRIVATE
		;
		;SET EDI TO BE RIGHT POINTER...
		;
		MOV	EAX,ECX
		MOV	EDI,ECX

		PUSH	ECX
		MOV	ECX,QN_BUFFER_PTR

		SHR	EAX,PAGE_BITS-2
		AND	EDI,PAGE_SIZE/4-1

		SHL	EDI,2
		MOV	EAX,[ECX+EAX*4+4]	;LOGICAL BLOCK ADDRESS

		POP	ECX
		ADD	EDI,EAX

		RET

Q_SET_MIDDLE_BLOCK	ENDP


QR_SORT2	PROC	NEAR	PRIVATE
		;
		;SORT [ESI] VS [EDI]
		;
		MOV	EAX,[ESI]
		MOV	EBX,[EDI]

		CONVERT	EAX,EAX,RELOC_GARRAY
		CONVERT	EBX,EBX,RELOC_GARRAY
		ASSUME	EAX:PTR RELOC_STRUCT
		ASSUME	EBX:PTR RELOC_STRUCT

		MOV	EDX,[EAX]._RL_FLAGS
		MOV	ECX,[EBX]._RL_FLAGS

		AND	DH,7
		AND	CH,7

		CMP	ECX,EDX
		JNZ	L1$

		MOV	ECX,[EAX]._RL_OS2_NUMBER
		MOV	EDX,[EBX]._RL_OS2_NUMBER

		CMP	EDX,ECX
		JZ	L3$

		CMP	ECX,100H
		JB	L4$

		CONVERT	ECX,ECX,IMPMOD_GARRAY
		ASSUME	ECX:PTR IMPMOD_STRUCT
		CONVERT	EDX,EDX,IMPMOD_GARRAY
		ASSUME	EDX:PTR IMPMOD_STRUCT

		MOV	ECX,[ECX]._IMPM_NUMBER
		MOV	EDX,[EDX]._IMPM_NUMBER
		ASSUME	ECX:NOTHING,EDX:NOTHING
L4$:
		CMP	EDX,ECX
L1$:
		JNC	L3$
		;
		;XCHG THEM
		;
;QEXCHANGE2:
		MOV	EAX,[ESI]
		MOV	EBX,[EDI]

		MOV	[EDI],EAX
		MOV	[ESI],EBX
L3$:
		RET

		ASSUME	EAX:NOTHING,EBX:NOTHING

QR_SORT2	ENDP


DEC_RIGHT_ESDI	PROC	NEAR	PRIVATE
		;
		;
		;
		MOV	EAX,QRIGHT_NUMBER
		SUB	EDI,4

		TEST	EAX,PAGE_SIZE/4 - 1
		JZ	L9$

		DEC	EAX

		MOV	QRIGHT_NUMBER,EAX

		RET

L9$:
		DEC	EAX

		MOV	QRIGHT_NUMBER,EAX
		MOV	EDI,EAX

		JMP	Q_SET_RIGHT_BLOCK

DEC_RIGHT_ESDI	ENDP


INC_LEFT_DSSI	PROC	NEAR	PRIVATE
		;
		;
		;
		MOV	EAX,QLEFT_NUMBER
		ADD	ESI,4

		INC	EAX

		MOV	QLEFT_NUMBER,EAX
		TEST	EAX,PAGE_SIZE/4 - 1

		JZ	L9$

		RET

L9$:
		MOV	ESI,EAX
		JMP	Q_SET_LEFT_BLOCK

INC_LEFT_DSSI	ENDP


		END

